A buffer memory constitutes a rapid, small-capacity interface between a processor and a generally slow, large-capacity data memory. The buffer memory is made up of a set of buffers intended to store extracts from the data memory. It can be a cache memory for receiving blocks of data from the data memory. The example chosen to illustrate the invention concerns the buffer memory of a DBMS. A DBMS is operated by the computer's operating system by means of a processor provided with virtual memory constituting all or part of the central memory of the computer and representative of the buffer memory. The extracts of data stored in the buffer memory are commonly pages of the refresh memory making up the data base. The buffer memory is therefore referred to as a pages cache memory. The management of the buffers in the cache memory is achieved by a buffer manager operated by the processor.
A distinction is usually made between two types of processing by the method, use of a buffer memory and, in particular, use of the pages cache memory in the example considered. The processing which frequently access a small number of pages in the cache memory is called local processing, and that less frequently accessing a large number of pages in the cache memory is referred to as non-local processing. For the simultaneous execution of local and non-local processing, the cache memory is divided under the control of the buffer manager. This division poses a major problem for managing the cache memory.
The buffer managers are currently and logically optimized for processing for local access. Ordinarily the cache memory is operated by an algorithm referred to as Least Recently Used (LRU). This algorithm draws up a list of the buffers in the cache memory according to the date of their last use. In principle, each time a buffer is referenced, the LRU rechains it to the head of the list. It follows that the buffers ahead of it in the list move down one place on the list. It is said that these buffers age by one place. When the buffer manager does not find a page in the cache memory, it requests the extraction of the page from the data base and its loading into the cache memory, while the LRU designates the buffer which was least recently referenced in order to record the new page. This optimization for local processing is especially unsuitable to the simultaneous operation of the cache memory for non-local processing. In effect, the access to new pages occurs much more frequently for non-local processing. There then follows a rapid modification of the head of the LRU list, and therefore a premature aging of the content of the other buffers. This premature aging greatly disturbs the management of local processing, and considerably slows down its execution.
Another problem, which stems from the rechaining at the head of the LRU list of the recently referenced buffers, arises especially in a multiprocessor environment. The rechaining to the head of the list must be independent in order to preserve the integrity of the list. In a multiprocessor system, this makes it necessary to take an exclusive lock during the dechaining and rechaining operation in order to move the buffer in the list. Taking an exclusive lock constitutes what is known as a critical section. A critical section can only be executed by a single processor at a given instant, and thus causes the multiprocessor's production to deteriorate.
The invention solves both these problems by permitting the optimization of the management of a set of buffers operated by local and non-local processing at the same time.